#include <iostream>
#include <memory>
#include <typeinfo>
using namespace std;

struct BlockHeader
{
    size_t size;       // 块总大小，包括头部
    bool isFree;       // 是否空闲
    BlockHeader *next; // 下一个空闲块指针
};
const size_t HEAP_SIZE = 1024 * 1024; // 1MB
char *heap = nullptr;
BlockHeader *freeList = nullptr;

void initializeHeap()
{
    heap = (char *)malloc(HEAP_SIZE);
    if (!heap)
    {
        std::cerr << "Failed to allocate heap memory." << std::endl;
        exit(1);
    }
    BlockHeader *firstBlock = (BlockHeader *)heap;
    firstBlock->size = HEAP_SIZE;
    firstBlock->isFree = true;
    firstBlock->next = nullptr;
    freeList = firstBlock;
}
void *myMalloc(size_t size)
{
    if (size == 0)
        return nullptr;

    size_t requiredSize = size + sizeof(BlockHeader);                   // 总需大小，包括头部
    const size_t MIN_BLOCK_SIZE = sizeof(BlockHeader) + sizeof(void *); // 最小块大小

    BlockHeader *current = freeList;
    BlockHeader *prev = nullptr;
    while (current != nullptr)
    {
        if (current->size >= requiredSize)
        {
            // 找到适合的块
            size_t remainingSize = current->size - requiredSize;
            if (remainingSize >= MIN_BLOCK_SIZE)
            {
                // 可分割，创建新空闲块
                BlockHeader *newBlock = (BlockHeader *)((char *)current + requiredSize);
                newBlock->size = remainingSize;
                newBlock->isFree = true;
                newBlock->next = current->next;
                if (prev != nullptr)
                    prev->next = newBlock;
                else
                    freeList = newBlock;

                current->size = requiredSize;
            }
            else
            {
                // 不可分割，从空闲列表移除
                if (prev != nullptr)
                    prev->next = current->next;
                else
                    freeList = current->next;
            }
            // 分配块，标记为非空闲
            current->isFree = false;
            // 返回用户数据区指针
            return (void *)((char *)current + sizeof(BlockHeader));
        }
        prev = current;
        current = current->next;
    }
    // 未找到适合块，返回 NULL
    return nullptr;
}
void myFree(void *ptr)
{
    if (ptr == nullptr)
        return;

    // 找到块头部
    BlockHeader *block = (BlockHeader *)((char *)ptr - sizeof(BlockHeader));

    // 标记为空闲
    block->isFree = true;

    // 加入空闲列表（头插法）
    block->next = freeList;
    freeList = block;

    // 检查与前一个块合并
    BlockHeader *current = freeList;
    BlockHeader *prev = nullptr;
    while (current != nullptr)
    {
        if (current != block && (char *)current + current->size == (char *)block)
        {
            // current 在 block 之前，可合并
            current->size += block->size;
            // 从空闲列表移除 block
            if (prev != nullptr)
                prev->next = block->next;
            else
                freeList = block->next;

            block = current;
            break;
        }
        prev = current;
        current = current->next;
    }

    // 检查与后一个块合并
    current = freeList;
    prev = nullptr;
    while (current != nullptr)
    {
        if (current != block && (char *)block + block->size == (char *)current)
        {
            // block 在 current 之前，可合并
            block->size += current->size;
            // 从空闲列表移除 current
            if (prev != nullptr)
                prev->next = current->next;
            else
                freeList = current->next;

            break;
        }
        prev = current;
        current = current->next;
    }
}